//给定两个数组，编写一个函数来计算它们的交集。 
//
// 
//
// 示例 1： 
//
// 输入：nums1 = [1,2,2,1], nums2 = [2,2]
//输出：[2]
// 
//
// 示例 2： 
//
// 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
//输出：[9,4] 
//
// 
//
// 说明： 
//
// 
// 输出结果中的每个元素一定是唯一的。 
// 我们可以不考虑输出结果的顺序。 
// 
// Related Topics 排序 哈希表 双指针 二分查找

package leetcode.editor.cn;

import java.util.HashSet;

public class IntersectionOfTwoArrays {
    public static void main(String[] args) {
        Solution solution = new IntersectionOfTwoArrays().new Solution();
        printArray(solution.intersection(new int[]{61,24,20,58,95,53,17,32,45,85,70,20,83,62,35,89,5,95,12,86,58,77,30,64,46,13,5,92,67,40,20,38,31,18,89,85,7,30,67,34,62,35,47,98,3,41,53,26,66,40,54,44,57,46,70,60,4,63,82,42,65,59,17,98,29,72,1,96,82,66,98,6,92,31,43,81,88,60,10,55,66,82,0,79,11,81},
                new int[]{5,25,4,39,57,49,93,79,7,8,49,89,2,7,73,88,45,15,34,92,84,38,85,34,16,6,99,0,2,36,68,52,73,50,77,44,61,48}));
        printArray(solution.intersection(new int[]{9,3,7},new int[]{6,4,1,0,0,4,4,8,7}));
        printArray(solution.intersection(new int[]{4,9,5},new int[]{9,4,9,8,4}));
        printArray(solution.intersection(new int[]{2,2},new int[]{2,2,1}));
        printArray(solution.intersection(new int[]{3,4,1},new int[]{3,4,1,6,8}));
        printArray(solution.intersection(new int[]{3},new int[]{3,4,1,6,8}));
        printArray(solution.intersection(null,new int[]{3,4,1,6,8}));
        printArray(solution.intersection(null,null));
        printArray(solution.intersection(null,new int[]{}));
        printArray(solution.intersection(new int[]{},null));
        printArray(solution.intersection(new int[]{},new int[]{3}));

    }

    public static void printArray(int array[]) {
        if (array != null) {
            for (int i : array) {
                System.out.println(i);
            }
            System.out.println("---------------------- end");
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] intersection(int[] nums1, int[] nums2) {
            int empty[] = new int[0];
            if (nums1 == null || nums2 == null) {
                return empty;
            }

            quitckSort(nums1, 0, nums1.length - 1);
            quitckSort(nums2, 0, nums2.length - 1);

            if (nums1.length <= nums2.length) {
                int[] sameIndexArray = new int[nums1.length];
                int i = 0;
                int ii = 0;
                for (; i < nums1.length; i++) {
                    for (int jj = 0; jj < nums2.length; jj++) {
                        if (nums1[i] == nums2[jj]) {
                            sameIndexArray[ii] = i;
                            ii++;
                            break;
                        }
                    }
                }

                if (ii == 0) {
                    return empty;
                }


                int result[] = new int[ii];
                int sameIndexArrayLength = ii;
                ii = 0;
                for (int j = 0; j < sameIndexArrayLength && ii < sameIndexArrayLength;
                     j++) {
                    int num = nums1[sameIndexArray[ii]];
                    result[j] = num;
                    ii++;
                }

                if (result.length == 0) {
                    return empty;
                }

                int dupCount = 0;
                int last = result[0];
                for (int j = 1; j < result.length; j++) {
                    if (last == result[j]) {
                        dupCount++;
                        last = result[j];
                    } else {
                        last = result[j];
                    }
                }

                int[] ret = new int[result.length - dupCount];
                last = result[0];
                ret[0] = result[0];
                for (int j = 1, k = 1; j < result.length && k < ret.length; j++) {
                    if (last == result[j]) {
                        last = result[j];
                    } else {
                        ret[k] = result[j];
                        k++;
                        last = result[j];
                    }
                }
                return ret;
            } else {
                int[] sameIndexArray = new int[nums2.length];
                int i = 0;
                int ii = 0;
                for (; i < nums2.length; i++) {
                    for (int jj = 0; jj < nums1.length; jj++) {
                        if (nums2[i] == nums1[jj]) {
                            sameIndexArray[ii] = i;
                            ii++;
                            break;
                        }
                    }
                }

                if (ii == 0) {
                    return empty;
                }


                int result[] = new int[ii];
                int sameIndexArrayLength = ii;
                ii = 0;
                for (int j = 0; j < sameIndexArrayLength && ii < sameIndexArrayLength;
                     j++) {
                    int num = nums2[sameIndexArray[ii]];
                    result[j] = num;
                    ii++;
                }


                if (result.length == 0) {
                    return empty;
                }

                int dupCount = 0;
                int last = result[0];
                for (int j = 1; j < result.length; j++) {
                    if (last == result[j]) {
                        dupCount++;
                        last = result[j];
                    } else {
                        last = result[j];
                    }
                }

                int[] ret = new int[result.length - dupCount];
                last = result[0];
                ret[0] = result[0];
                for (int j = 1, k = 1; j < result.length && k < ret.length; j++) {
                    if (last == result[j]) {
                        last = result[j];
                    } else {
                        ret[k] = result[j];
                        k++;
                        last = result[j];
                    }
                }
                return ret;
            }

        }


        private void quitckSort(int[] array, int leftBound,
                                int rightBound) {
            if (leftBound >= rightBound) {
                return;
            }

            int i = leftBound;
            int j = rightBound;
            int pivot = array[leftBound];

            while (i < j) {
                int currentOfRight;
                while ((currentOfRight = array[j]) >= pivot && i < j) {
                    j--;
                }

                int currentOfLeft;
                while ((currentOfLeft = array[i]) <= pivot && i < j) {
                    i++;
                }

                if (i < j) {
                    array[i] = currentOfRight;
                    array[j] = currentOfLeft;
                }
            }

            // 交换 array[i/j] 与array[left]
            array[leftBound] = array[i];
            array[i] = pivot;

            quitckSort(array, leftBound, i - 1);
            quitckSort(array, i + 1, rightBound);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}